In a coding technology based on a code excited linear prediction (CELP) model, it is a very important process to perform quantization coding on residual signals after adaptive filtering. Currently, quantization coding of the residual signals is often performed through fixed codebook searching. A commonly used fixed codebook is an algebraic codebook. The algebraic codebook focuses on pulse positions of target signals, and sets the pulse amplitude to 1 by default, so that only the symbols and positions of the pulses need to be quantified. Certainly, multiple pulses may be superposed at the same position to denote different amplitudes. When the algebraic codebook is employed for quantization coding, it is important to search positions of pulses in the optimal algebraic codebook corresponding to the target signal. Generally, during the search for optimal positions of the pulses, the computation of a full search (that is, to traverse all possible position combinations) is quite complicated, and thus a sub-optimal search algorithm is needed. On the basis of ensuring the quality of the search result, how to reduce the search times and lower down the computation complexity is the main issue to be studied and solved in the coding technology.
Two existing sub-optimal search methods for searching pulse positions in an algebraic codebook are described as follows.
1. Depth-First Tree Search Procedure
It is assumed that the length of a speech sub-frame is 64 and a pulse number to be searched is N which changes with the code rate. With no other restrictions, the computation for searching N pulses in 64 positions is highly complicated. Therefore, the pulse positions in the algebraic codebook are restrained, and the 64 positions are divided into M tracks. A typical method for dividing the tracks is shown in Table 1.
TABLE 1TrackPositionsT00, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60T11, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61T22, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62T33, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63
In Table 1, “T0” to “T3” are four tracks, and “Positions” are position numbers on each track. It is known from Table 1, 64 positions are divided into 4 tracks, each track has 16 positions, and pulse positions on the four tracks are staggered, so as to ensure various combinations of the pulse positions to the maximum.
The N pulses to be searched are restrained on M=4 tracks based on a certain quantity distribution. For example, N=4 and one pulse is searched on each track. Other circumstances may be deduced likewise.
It is assumed that the pulses to be searched on T0 to T3 are respectively P0 to P3. During the search, two pulses on two adjacent tracks are searched at a time, for example, T0-T1, T1-T2, T2-T3, and T3-T0, so that a final optimal codebook is obtained through a four-level search. The detailed process is shown in FIG. 1, which includes the following steps.
1) A first level search is performed on T0-T1 and T2-T3. Firstly, positions of P0 and P1 are searched on T0-T1, in which P0 is searched from 4 positions among 16 positions on the track T0, the 4 positions are determined by extreme values of known reference signals on the track, and P1 is searched from 16 positions on the track T1. Optimal positions of P0 and P1 are determined from the searched 4×16 position combinations according to a set evaluation criterion (for example, a cost function Qk). Afterward, the positions of P2 and P3 are searched on T2-T3, in which P2 is searched from 8 positions among 16 positions on the track T2, the 8 positions are determined by extreme values of known reference signals on the track, and P3 is searched from 16 positions on the track T3, so that the optimal positions of P2 and P3 are determined. Thus, the search process on this level is completed.
2) A second level search is performed on T1-T2 and T3-T0, which is similar to the first level search.
3) A third level search is performed on T2-T3 and T0-T1, and a fourth level search is performed on T3-T0 and T1-T2 similarly.
4) Finally, an optimal result is selected from the four-level search as an optimal algebraic codebook. The total search times are 4×(4×16+8×16)=768.
2. Global Pulse Replacement Procedure
For ease of illustration, it is assumed that the same codebook structure as that of the previous algorithm is used, one pulse is searched on each of the 4 tracks, and the pulses searched on T0 to T3 are respectively P0 to P3. The detailed process includes the following steps.
1) An initial codebook is determined, which is assumed to be {P0, P1, P2, P3}={20, 33, 42, 7}. P1, P2, and P3 remain unchanged, the initial value 20 of P0 is sequentially replaced by other positions on the track T0, so as to obtain new codebooks {0, 33, 42, 7}, {4, 33, 42, 7}, . . . , {60, 33, 42, 7}. According to a set evaluation criterion, an optimal new codebook is selected, for example, a new codebook having a maximum Qk value of the cost function is selected. The maximum Qk value and the corresponding new codebook are recoded, for example, {4, 33, 42, 7}.
2) P0, P2, and P3 in the initial codebook remain unchanged (it should be noted that the initial codebook here is still the original initial codebook, i.e., {20, 33, 42, 7}), the initial value 33 of P1 is sequentially replaced by other positions on the track T1, which is similar to the process in 1), so as to obtain a maximum Qk value and a corresponding new codebook, for example, {20, 21, 42, 7} through the replacement.
3) Processes similar to 1) and 2) are performed on P2 and P3, so as to respectively obtain a maximum Qk value and a corresponding new codebook.
4) A maximum value is selected from the obtained four maximum Qk values as a global optimal value, and the corresponding codebook, for example, {20, 21, 42, 7}, serves as an optimal codebook for the search of this round.
5) The optimal codebook {20, 21, 42, 7} is taken as an initial codebook for a new round, the processes from 1) to 4) are then repeated, and this cycle is generally performed for four times to obtain a final optimal codebook. Therefore, the total search times are 4×(4×16)=256
It is difficult for the codebook search algorithms used in various existing coding technologies to meet the requirements for computation complexity and performance. For example, though the depth-first tree search algorithm obtains a desired speech quality under various code rates, the search times are large, and the computation complexity is high. In addition, though the global pulse replacement algorithm has a low computation complexity, a local maximum value may occur, so that the performance is unstable. That is, the algorithm may achieve a good quality under certain signal conditions, but may fail to achieve an desirable quality under other signal conditions.